'''我实现的遗传算法功能'''
import Game
import Map
import numpy as np
import random as rd

'''
函数所有变量表示：
clickNum  玩家点击次数
pNum      指针的数量，即指针标号的上界
size_pop  种群数量
pc        交叉率
prob_mut  基因的变异率
'''
history_fitV = []  # 种群适应度的记录，每一行都有一次迭代的种群适应度
history_king = []  # 种群最佳个体基因的记录

"""生成初始种群"""
def crtpopula(size_pop, clickNum, pNum): 
    popula = np.random.randint(low=0, high=pNum, size=(size_pop, clickNum))# 生成size_pop行, clickNum列的矩阵，矩阵的每一行表示一个个体，每个个体有clickNum个基因，基因取值范围是[0, pNum)
    return popula

"""锦标赛选择"""
def selection_tournament(level, popula, size_pop, tourn_size=3): # 顺便记录新种群的适应度和最佳个体
    '''
    适应度比值太小时轮盘赌的比例太均匀，优势个体不容易被选中，所以采用选拔赛的方式
    生成size_pop组小队，每小队随机选tourn_size个人，选择小队里的最佳个体（选出size_pop个人）
    同时记录选出个体的信息（适应度及最佳基因型）
    返回： 选择出大小为size_pop的种群和最优适应度
    '''
    popNum = len(popula)
    FitV = np.array([Game.star(eval("Map.map"+str(level)), eval("Map.index"+str(level)), popula[i]) for i in range(popNum)]) # 种群适应度
    aspirants_idx = np.random.randint(popNum, size=(size_pop, tourn_size))     # 按地址随机生成size_pop个小队，从size_pop个小队中选出size_pop个人                                
    aspirants_values = FitV[aspirants_idx]                                     # 每个小队成员的适应度
    winnerId = aspirants_values.argmax(axis=1)  # winner index in every team   # 每个小队冠军在小队中的位置
    sel_index = [aspirants_idx[i, j] for i, j in enumerate(winnerId)]          # 根据小队冠军在小队中的地址得出小队冠军在种群中的地址
    newPopula = popula[sel_index]                                              # 筛选出的所有小队冠军构成下一代
    newFitV = FitV[sel_index]                                                  # 下一代与之对应的适应度
    king = newPopula[ newFitV.argmax() ]
    history_fitV.append(newFitV)                                               
    history_king.append(king) 
    return newPopula

"""变异"""
def mutation(popula, clickNum, pNum, prob_mut): 
    '''
    按照prob_mut的概率，每个基因都可能变异成另外一个[0, pNum)的随机的基因
    '''
    mask = (eval('np.random.rand' + str(popula.shape)))
    for i in range(len(popula)):
        for j in range(clickNum):
            if(mask[i, j] < prob_mut):
                popula[i, j] = rd.randint(0, pNum-1)

"""1点交叉繁殖"""
def breed_1point(popula, clickNum, pc):
    newpop = []
    popNum = len(popula)
    idx = np.random.permutation(range(popNum))     # 先打乱个体次序
    for i in range(0, popNum, 2):
        if(rd.random() < pc):
            n = np.random.randint(0, clickNum)     # 基因[n:]交叉
            son1, son2 = np.array(popula[idx[i]]), np.array(popula[idx[i+1]])  # np.array比np.copy更快，也不会修改原父母
            son1[n:], son2[n:] = popula[idx[i+1], n:], popula[idx[i], n:]
            newpop += [son1, son2]
    return np.concatenate((popula, newpop))


"""2点交叉繁殖"""
def breed_2point(popula, clickNum, pc):
    '''
    每两个亲本以pc概率交叉随机生成两个儿子，繁殖出的新个体加入种群
    新增个体数量的期望是 popNum * pc
    '''
    newpop = []
    popNum = len(popula)
    idx = np.random.permutation(range(popNum))           # 先打乱个体次序
    for i in range(0, popNum, 2):                        # 选出popula的第idx[i]个与popula的第idx[popNum // 2 + i]个交叉
        if(rd.random() < pc):
            n1, n2 = np.random.randint(0, clickNum+1, 2) # 基因[n1:n2)交叉，取值范围[0,10]
            if n1 > n2:
                n1, n2 = n2, n1
            son1, son2 = np.array(popula[idx[i]]), np.array(popula[idx[i+1]])  # np.array比np.copy更快，也不会修改原父母
            son1[n1:n2], son2[n1:n2] = popula[idx[i+1], n1:n2], popula[idx[i], n1:n2]
            newpop += [son1, son2]                      # 比 newpop += list(son) 省时
    return np.concatenate((popula, newpop))

'''均匀点交叉繁殖'''
def uniform_point(popula, clickNum, pc):
    newpop = []
    popNum = len(popula)
    idx = np.random.permutation(range(popNum))           # 先打乱个体次序
    for i in range(0, popNum, 2):
        if(rd.random() < pc):
            son1, son2 = np.array(popula[idx[i]]), np.array(popula[idx[i+1]])
            for n in range(clickNum):
                if(rd.randint(0,1) == 1):
                    temp = son1[n]
                    son1[n] = son2[n]
                    son2[n] = temp
            newpop += [son1, son2]
    return np.concatenate((popula, newpop))

'''1点交叉'''
def crossover_1point(popula, clickNum, pc):
    popNum = len(popula)
    idx = np.random.permutation(range(popNum)) # 先打乱个体次序
    for i in range(0, popNum, 2):
        n = np.random.randint(0, clickNum)     # 基因[n:]交叉
        seg1, seg2 = popula[idx[i], n:].copy(), popula[idx[i+1], n:].copy()
        popula[idx[i], n:], popula[idx[i+1], n:] = seg2, seg1
    return popula

'''2点交叉'''
def crossover_2point(popula, clickNum, pc):
    popNum = len(popula)
    idx = np.random.permutation(range(popNum))       # 先打乱个体次序
    for i in range(0, popNum, 2):
        n1, n2 = np.random.randint(0, clickNum+1, 2) # 基因[n1:n2)交叉，取值范围[0,10]
        if n1 > n2:
            n1, n2 = n2, n1
        seg1, seg2 = popula[idx[i], n1:n2].copy(), popula[idx[i+1], n1:n2].copy()
        popula[idx[i], n1:n2], popula[idx[i+1], n1:n2] = seg2, seg1
    return popula

'''运行实验'''
def run(level, size_pop, clickNum, pNum, max_iter, pc, prob_mut): # 运行MyGA，返回种群历史适应度
    popula= selection_tournament(level, crtpopula(size_pop, clickNum, pNum), size_pop )
    iter = 0
    while(iter < max_iter):
        popula = breed_2point(popula, clickNum, pc) # 从这修改交叉算子
        mutation(popula, clickNum, pNum, prob_mut)
        popula= selection_tournament(level, popula, size_pop)
        iter += 1
    return history_king, history_fitV